from CarData import CarData
from Attributes import Attributes
from math import log2
from Tree import *

#
#   Returns a list with all elements that matches 
#   with the given function
#
def FindAll(list, func) :
    result = []
    for item in list :
        if func(item) :
            result.append(item)
    return result

#
#   Counts how many elements in a list that matches
#   with the given function
#
def CountAll(list, func) :
    count = 0
    for item in list :
        if func(item) :
            count += 1
    return count

#
#   Class for learning a DecisionTree
#
class DecisionTree :
    def __init__(self) :
        self.data = []        
        self.tree = DecisionLeaf("N/A")

    #
    #   Reads examples for learning from a textfile
    #
    def ReadFromFile(self, filename) :
        self.data.clear()
        fin = open(filename)
        for dataline in fin.readlines() :
            data = dataline.split(',')
            if len(data) == 7 :
                if data[6][-1:] == '\n' :
                    data[6] = data[6][:-1]
                self.data.append(CarData(data[0], data[1], data[2], data[3], data[4], data[5], data[6]))
        fin.close()
        del fin
        del dataline
        del data

    #
    #   Use loaded examples to create a DecisionTree
    #
    def learn(self) :
        self.tree = self.ID3(self.data, ["buying", "maint", "doors", "persons", "lug_boot", "safety"])

    #
    #   ID# DecisionTree Algortihm
    #
    def ID3(self, Examples, AttributeList) :
        #   if all results in the example list are equal
        if CountAll(Examples, lambda x : x.attributes["attractiveness"].GetValue() != Examples[0].attributes["attractiveness"].GetValue()) == 0 :
            return DecisionLeaf(Examples[0].attributes["attractiveness"].GetValue())
        #   if there are no attributes left to check
        elif len(AttributeList) == 0 :
            return DecisionLeaf(self.GetMostCommon(Examples, "attractiveness"))
        else :
            A = self.GetBestIGAttribute(Examples, AttributeList)
            T = DecisionFork(A, {})
            for value in Attributes.Domains[A] :
                Examples_value = FindAll(Examples, lambda x : x.attributes[A].GetValue() == value)
                if len(Examples_value) == 0 :
                    T.add(value, DecisionLeaf(self.GetMostCommon(Examples, "attractiveness")))
                else :
                    AttributeList.remove(A)
                    T.add(value, self.ID3(Examples_value, AttributeList))
                    AttributeList.append(A)
        return T 

    #
    #   Calculates the entropy in the given examplelist
    #
    def CalculateEntropy(self, Examples, Attribute) :
        entropy = 0
        for value in Attributes.Domains[Attribute] :
            p = CountAll(Examples, lambda x : x.attributes[Attribute].GetValue() == value) / len(Examples)
            if p != 0 :
                entropy +=  -p * log2(p)
        return entropy

    #
    #   Calculated the information gain for the given attribute in
    #   the given examplelist
    #
    def InformationGain(self, Examples, Attribute) :
        HS = self.CalculateEntropy(Examples, "attractiveness")
        HA = 0
        for value in Attributes.Domains[Attribute] :
            E_value = FindAll(Examples, lambda x : x.attributes[Attribute].GetValue() == value)
            if len(E_value) != 0:
                HA += (len(E_value)/len(Examples))*self.CalculateEntropy(E_value, "attractiveness")
        return HS - HA

    #
    #   Returns the attribut that has the greatest information gain 
    #
    def GetBestIGAttribute(self, Examples, Attributes) :
        bestA = Attributes[0]
        bestIG = self.InformationGain(Examples, Attributes[0])
        for i in range(1,len(Attributes)) :
            if (self.InformationGain(Examples, Attributes[i]) > bestIG) :
                bestA = Attributes[i]
        return bestA

    #
    #   Returns the most common result from the given examplelist
    #
    def GetMostCommon(self, Examples, Attribute) :
        count = {}
        for value in Attributes.Domains[Attribute] :
            count[value] = 0
        for item in Examples : 
            count[item.attributes[Attribute].GetValue()] += 1
        mostCommon = ""
        commonCount = 0
        for item in count :
            if count[item] > commonCount :
                commonCount = count[item]
                mostCommon = item
        return mostCommon